<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉搜索树前驱路径</title>
    <script src="https://d3js.org/d3.v7.min.js"></script>
    <style>
        .node {
            fill: lightblue;
            stroke: black;
            stroke-width: 1.5px;
            cursor: pointer;
        }

        .link {
            fill: none;
            stroke: #ccc;
            stroke-width: 2px;
        }

        .clicked {
            fill: orange;
        }

        .error {
            fill: red;
        }

        #message {
            font-size: 20px;
            font-weight: bold;
            margin-top: 20px;
        }

        #path {
            font-size: 16px;
            font-weight: bold;
            margin-top: 10px;
        }
    </style>
</head>
<body>
<h1>请选择查询 <span id="random-node-name"></span> 的前驱节点路径</h1>
<svg width="600" height="400"></svg>
<div id="message"></div>
<div id="path">前驱节点路径：<span id="predecessor-path"></span></div>

<script>
    function insert(root, name) {
        if (root === null) {
            return {name: name, left: null, right: null};
        }

        if (name < root.name) {
            root.left = insert(root.left, name);
        } else if (name > root.name) {
            root.right = insert(root.right, name);
        }

        return root;
    }

    function generateRandomBST(minNodes, maxNodes) {
        let root = null;
        const values = Array.from({length: maxNodes - minNodes + 1}, (_, i) => i + minNodes);

        for (let i = values.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [values[i], values[j]] = [values[j], values[i]];
        }

        values.forEach(value => {
            root = insert(root, value);
        });

        return root;
    }

    function convertToD3Hierarchy(node) {
        if (!node) return {name: null, children: []};
        return {
            name: node.name,
            children: [
                convertToD3Hierarchy(node.left),
                convertToD3Hierarchy(node.right)
            ]
        };
    }

    function findPath(root, target, path = []) {
        if (root === null) return null;

        path.push(root.name);

        if (root.name === target) {
            return path;
        }

        if (target < root.name) {
            return findPath(root.left, target, path);
        } else {
            return findPath(root.right, target, path);
        }
    }

    function findPredecessorNode(root, targetNode) {
        let currentNode = root;
        let predecessor = null;

        while (currentNode) {
            if (targetNode < currentNode.name) {
                currentNode = currentNode.left;
            } else if (targetNode > currentNode.name) {
                predecessor = currentNode;
                currentNode = currentNode.right;
            } else {
                if (currentNode.left) {
                    predecessor = currentNode.left;
                    while (predecessor.right) {
                        predecessor = predecessor.right;
                    }
                }
                break;
            }
        }

        return predecessor;
    }

    function findPredecessorPath(root, target) {
        let predecessorNode = findPredecessorNode(root, target.name);
        if (!predecessorNode) return null;
        debugger
        if (target.left == null) {
            return findPath(root, predecessorNode.name, []);
        }else {
            return findPath(target, predecessorNode.name, []);
        }
    }

    let treeData = generateRandomBST(1, 15);
    const d3TreeData = convertToD3Hierarchy(treeData);

    const allNodes = [];
    const nodeMap = {};

    function collectNodes(node) {
        if (!node) return;
        if (node.name !== null) {
            allNodes.push(node.name);
            nodeMap[node.name] = node;
        }
        if (node.children) {
            node.children.forEach(collectNodes);
        }
    }

    function findNodeByName(node, name) {
        if (!node) return null;
        if (node.name === name) return node;
        return findNodeByName(node.left, name) || findNodeByName(node.right, name);
    }

    collectNodes(d3TreeData);

    const randomNodeName = allNodes[Math.floor(Math.random() * allNodes.length)];
    const randomNode = findNodeByName(treeData, randomNodeName);
    document.getElementById("random-node-name").innerText = randomNodeName;

    const predecessorPath = findPredecessorPath(treeData, randomNode);
    document.getElementById("predecessor-path").innerText = predecessorPath ? predecessorPath.join(" -> ") : '没有前驱节点路径';

    let userClickIndex = 0;
    const width = 600;
    const height = 400;

    const svg = d3.select("svg");

    const treeLayout = d3.tree().size([width - 100, height - 100]);
    const root = d3.hierarchy(d3TreeData);
    treeLayout(root);

    svg.selectAll(".link")
        .data(root.links())
        .enter().filter(d => d.source.data.name !== null && d.target.data.name !== null)
        .append("line")
        .attr("class", "link")
        .attr("x1", d => d.source.x + 50)
        .attr("y1", d => d.source.y + 50)
        .attr("x2", d => d.target.x + 50)
        .attr("y2", d => d.target.y + 50);

    const nodes = svg.selectAll(".node")
        .data(root.descendants())
        .enter().filter(d => d.data.name !== null)
        .append("circle")
        .attr("class", "node")
        .attr("cx", d => d.x + 50)
        .attr("cy", d => d.y + 50)
        .attr("r", 20)
        .on("click", function (event, d) {
            handleNodeClick(d);
        });

    svg.selectAll(".label")
        .data(root.descendants())
        .enter()
        .append("text")
        .attr("x", d => d.x + 50)
        .attr("y", d => d.y + 50)
        .attr("dy", 5)
        .attr("text-anchor", "middle")
        .text(d => d.data.name);

    function handleNodeClick(node) {
        const clickedNodeName = node.data.name;

        if (clickedNodeName === predecessorPath[userClickIndex]) {
            d3.select(event.target)
                .classed("clicked", true);
            userClickIndex++;
            showMessage("正确，继续点击后续节点");
            if (userClickIndex === predecessorPath.length) {
                showMessage("成功，前驱节点路径正确！");
            }
        } else {
            d3.select(event.target)
                .classed("error", true);
            showMessage("错误，请重新开始！");
            userClickIndex = 0;  // 重置用户点击的索引
        }
    }

    function showMessage(message) {
        document.getElementById("message").innerText = message;
    }
</script>
</body>
</html>
